package Heap;

import java.util.Arrays;

public class Heap {
    public int[] elem;
    public int usedSize;

    public Heap() {
        this.elem = new int[10];
    }

    //创建一个大根堆,时间复杂度O(N)
    public void createHeap(int[] array) {
        for(int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        //调整为大根堆（向下调整）
        for(int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            shiftDown(parent,usedSize);
        }
    }

    /**
     *
     * @param parent 代表每棵子树的根节点
     * @param len 代表每棵子树的结束位置
     */
    private void shiftDown(int parent,int len) {
        int child = parent * 2 + 1;
        //是不是一定有左孩子
        while(child < len) {
            //不能保证一定有右孩子
            if(child + 1 < len && elem[child] < elem[child + 1]) {
                child = child+1;
            }
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = parent*2 +1;
            }else {
                //此时本身就是一个大根堆
                break;
            }
        }
    }

    /**
     * 插入数据
     * 1.插入到数组的最后位置；2.向上调整，孩子结点跟父亲节点比较，孩子结点大就跟父亲结点交换（大根堆）
     * 向上调整，孩子与父亲比较； 向下调整：父亲与孩子比较
     */

    public void push(int val) {
        //检查满
        if(isFull()) {
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        //存数据
        elem[usedSize] = val;
        usedSize++;
        shiftUp(usedSize-1);
    }

    private boolean isFull() {
        return usedSize == elem.length;
    }

    //向上调整建堆时间复杂度：O(N*logN)
    private void shiftUp(int child) {
        int parent = (child - 1)/2;
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child - 1)/2;
            }else {
                break;
            }
        }
    }


    /**
     * 删除元素 只能删除堆顶元素，1.堆顶元素0下标和最后一个元素交换，然后最后一个元素不算入堆里面的数据
     * 此时都是大根堆，只有0下标不是大根堆，2.所以需要向下调整0下标的元素；3.此时调整的结束位置有变化，最后一个结点不调整
     *
     */

    public void poll() {
        if(empty()) {
            throw new HeapEmptyException("优先级队列为空！");
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        shiftDown(0,usedSize);
    }

    private boolean empty() {
        return usedSize==0;
    }


    //获取堆顶元素
    public int peek() {
        if(empty()) {
            throw new HeapEmptyException("优先级队列为空！");
        }
        return elem[0];
    }

    /**
     * 堆排序
     * 0.建立大根堆 O(N) 在堆排序中，这个复杂度可以省略
     * 1.交换0和最后一个下标位置的元素
     * 2.对0下标的位置进行向下调整
     * HeapSort这个方法的时间复杂度为：O(N*logN)
     * 升序---建大堆
     * 降序---建小堆
     */
    public void HeapSort() {
        int end = usedSize - 1;
        while(end > 0) {
            int temp = elem[0];
            elem[0] = elem[end];
            elem[end] = temp;
            shiftDown(0,end);
            end--;
        }
    }
}

